\subsection{Graphs of a given diameter}
\begin{definition}
	Let \( G \) be a connected graph.
	The \emph{diameter} of \( G \) is
	\[ \diam G = \max \qty{d(x,y) \mid x, y \in V(G)} \]
\end{definition}
\begin{remark}
	The diameter of \( G \) is 1 if and only if \( G \) is complete, so there are \( \binom n 2 \) edges.
\end{remark}
\begin{proposition}
	Let \( G \) be a graph with diameter at most 2.
	Then \( \abs{G} \leq \Delta(G)^2 + 1 \).
\end{proposition}
\begin{proof}
	Let \( x \in G \).
	Then \( V(G) = \qty{x} \cup N(x) \cup N(N(x)) \setminus N(x) \).
	Hence \( \abs{G} \leq 1 + \Delta(G) + \Delta(G)(\Delta(G) - 1) \leq \Delta(G)^2 + 1 \).
\end{proof}
\begin{definition}
	A \emph{Moore graph} is a graph for which \( \abs{G} = \Delta(G)^2 + 1 \).
\end{definition}
\begin{remark}
	Any Moore graph is regular.
	Such a graph does not contain a triangle.
	A graph \( G \) is a Moore graph if and only if every distinct \( x, y \in V(G) \) have a unique path of length at most 2 between them.
\end{remark}
\begin{example}
	\( C_5 \) is a Moore graph with \( \Delta(C_5) = 2 \).
	The Petersen graph is a Moore graph with degree 3.
\end{example}

\subsection{Adjacency matrices}
\begin{definition}
	The \emph{adjacency matrix} of a graph \( G \) on vertex set \( \qty{1, \dots, n} \) is the \( n \times n \) matrix \( A_G \) with entries \( a_{xy} = \symbb 1_{xy \in E(G)} \).
\end{definition}
\begin{remark}
	Adjacency matrices are symmetric and have zero diagonal, hence \( \tr A_G = 0 \).
\end{remark}
\begin{proposition}
	Let \( G \) be a graph, and \( A_G \) be its adjacency matrix.
	Let \( k \in \mathbb N \).
	Then \( (A_G^k)_{xy} \) is the number of walks of length \( k \) from \( x \) to \( y \) in \( G \).
\end{proposition}
\begin{proof}
	If \( k = 1 \), then the theorem clearly holds.
	If \( k = 2 \), then \( (A_G^2)_{xy} = \sum_z (A_G)_{xz} (A_G)_{zy} = \sum_z \symbb 1_{x \sim z \in E} \symbb 1_{z \in y} \) counts the amount of walks of length 2.
	For \( k > 2 \), we can proceed by induction.
\end{proof}
\( A_G \) acts on \( \mathbb R^n \) as it is a linear map.
\begin{example}
	Consider the graph \( C_4 \) on vertex set \( \qty{1, 2, 3, 4} \).
	This has adjacency matrix
	\[ A_{C_4} = \begin{pmatrix}
		0 & 1 & 0 & 1 \\
		1 & 0 & 1 & 0 \\
		0 & 1 & 0 & 1 \\
		1 & 0 & 1 & 0
	\end{pmatrix} \]
	Let \( x = (1, 2, -2, 3)^\transpose \).
	Then \( A_G x = (5, -1, 5, -1)^\transpose \).
	Note that \( (A_G x)_y \) is the sum of \( x_z \) for \( z \sim y \).
\end{example}
\begin{proposition}
	Let \( A \) be an \( n \times n \) symmetric matrix.
	Then \( A \) has real eigenvalues \( \lambda_i \), and there exists an orthonormal basis \( u_i \) where \( A u_i = \lambda_i u_i \).
\end{proposition}
Given a graph \( G \) on \( n \) vertices, we can now consider its eigenvalues and eigenvectors, which are the eigenvalues and eigenvectors of \( A_G \).
Let \( \lambda_{\mathrm{max}} = \lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_n = \lambda_{\mathrm{min}} \) without loss of generality.
Since \( \sum_{i=1}^n \lambda_i = \tr A_G = 0 \), if \( G \) is a nonempty graph, \( \lambda_{\mathrm{max}} > 0 \) and \( \lambda_{\mathrm{min}} < 0 \).
\begin{example}
	\( (1, 1, 1, 1)^\transpose \) is an eigenvector of \( C_4 \) with eigenvalue 2.
	Note that the rank of \( A_G \) is 2, so there are two zero eigenvalues.
	Since the eigenvalues sum to zero, \( \lambda_{\mathrm{min}} = -2 \).
	One example of a corresponding eigenvector is \( (1, -1, 1, -1)^\transpose \).
\end{example}
\begin{proposition}
	Let \( A \) be a symmetric \( n \times n \) matrix.
	Then
	\[ \lambda_{\mathrm{max}} = \max_{x \in \mathbb R^n \setminus \qty{0}}\qty( \frac{\inner{x, Ax}}{\inner{x, x}} ); \quad \lambda_{\mathrm{min}} = \min_{x \in \mathbb R^n \setminus \qty{0}}\qty( \frac{\inner{x, Ax}}{\inner{x, x}} ) \]
\end{proposition}
\begin{proposition}
	Let \( G \) be a graph.
	\begin{enumerate}
		\item If \( \lambda \) is an eigenvalue, then \( \abs{\lambda} \leq \Delta(G) \).
		\item If \( G \) is connected, then \( \Delta(G) \) is an eigenvalue if and only if \( G \) is regular.
			In this case, \( \symbb 1 = (1, \dots, 1) \) is the corresponding eigenvector, and \( \Delta(G) \) has multiplicity 1.
		\item If \( G \) is connected, then \( -\Delta(G) \) is an eigenvalue if and only if \( G \) is regular and bipartite.
		\item \( \lambda_{\mathrm{max}} \geq \delta(G) \).
	\end{enumerate}
\end{proposition}
\begin{proof}
	\emph{Part (i).}
	Let \( \lambda \) be an eigenvalue for \( G \).
	Let \( x = (x_1, \dots, x_n) \) be a corresponding eigenvector.
	Let \( x_i \) be the entry with largest absolute value.
	We may assume that \( x_i = 1 \).
	Then, \( \lambda x = Ax \) gives
	\[ \lambda = \lambda x_i = (\lambda x)_i = (Ax)_i = \sum_{j \sim i} x_j \implies \abs{\lambda} \leq \abs{\sum_{j \sim i} x_j} \leq \Delta(G) \]
	\emph{Part (ii).}
	Suppose \( G \) is regular.
	Then observe that \( \symbb 1 = (1, \dots, 1) \) is an eigenvector of \( G \) with eigenvalue \( \delta(G) = \Delta(G) \).
	Now suppose \( \Delta(G) \) is an eigenvalue.
	Let \( x = (x_1, \dots, x_n) \) be a corresponding eigenvector and let \( x_i \) be the entry with largest absolute value.
	Without loss of generality let \( x_i = 1 \).
	We have \( \Delta(G) = \Delta(G) x_i = \sum_{j \sim i} x_j \), so \( \deg i = \Delta(G) \), and if \( j \sim i \), then \( x_j = 1 \).
	Proceeding inductively, since the graph is connected, all \( x_j \) are equal to 1, and all vertices have degree \( \Delta(G) \).
	So \( x = \symbb 1 \) as required.
	Since this is the only possible eigenvector with eigenvalue \( \Delta(G) \), and \( A_G \) is symmetric, the multiplicity of the eigenvalue \( \Delta(G) \) is 1.

	\emph{Part (iii).}
	Suppose \( G \) is bipartite and regular.
	Let \( V(G) = X \sqcup Y \), and consider the vector given by \( x_i = 1 \) if \( i \in X \) and \( x_i = -1 \) if \( i \in Y \).
	Then \( Ax = -\Delta(G) x \) as required.
	Now suppose \( -\Delta(G) \) is an eigenvalue.
	As before, let \( x \) be an eigenvector with \( x_i = 1 \) of maximal absolute value.
	We have \( -\Delta(G) = -\Delta(G) x_i = \sum_{j \sim i} x_j \), hence \( \deg i = \Delta(G) \), and if \( j \sim i \), we have \( x_j = -1 \).
	Since \( G \) is connected, we repeat the process to show that \( G \) is \( \Delta(G) \)-regular, and \( x_j \) is either \( +1 \) or \( -1 \) giving a natural bipartition of the graph.

	\emph{Part (iv).}
	Note that
	\[ \lambda_{\mathrm{max}} = \max_{x \in \mathbb R^n \setminus \qty{0}} \frac{\inner{x, Ax}}{\inner{x,x}} \]
	Consider \( x = \symbb 1 = (1, \dots, 1) \).
	Then
	\[ \lambda_{\mathrm{max}} \geq \frac{\inner{\symbb 1, A\symbb 1}}{\inner{\symbb 1, \symbb 1}} = \frac{1}{n} \sum_{i=1}^n \deg(i) \geq \delta(G) \]
\end{proof}

\subsection{Strongly regular graphs}
\begin{definition}
	A graph \( G \) is \emph{\( (k, a, b) \)-strongly regular} if
	\begin{enumerate}
		\item \( G \) is \( k \)-regular;
		\item for every pair of adjacent vertices \( x \sim y \), they have exactly \( a \) common neighbours, so \( \abs{N(x) \cap N(y)} = a \);
		\item for every pair of not equal and non-adjacent vertices \( x \not\sim y \), they have exactly \( b \) common neighbours, so \( \abs{N(x) \cap N(y)} = b \).
	\end{enumerate}
\end{definition}
\begin{example}
	\( C_4 \) is \( (2, 0, 2) \)-strongly regular.
	\( C_5 \) is \( (2, 0, 1) \)-strongly regular.
	Any Moore graph is \( (\Delta(K), 0, 1) \)-strongly regular.
	% The following graph
	% % TODO: diagram
	% is \( (4, 1, 1) \)-strongly regular.
\end{example}
\begin{theorem}[strongly regular graphs are rare]
	Let \( G \) be a \( (k, a, b) \)-strongly regular graph on \( n \) vertices.
	Then,
	\[ \frac{1}{2}\qty((n-1) \pm \frac{(n-1)(b-a) - 2k}{\sqrt{(a-b)^2 + 4(k-b)}}) \]
	are integers.
\end{theorem}
\begin{proof}
	Let \( A \) be the adjacency matrix of \( G \).
	Then
	\[ (A^2)_{xy} = \begin{cases}
		a & x \sim y \\
		b & x \neq y, x \not\sim y \\
		k & x = y
	\end{cases} \implies A^2 = aA + b(J-I-A) + kI \]
	where \( J \) is the matrix with \( J_{xy} = 1 \) for all \( x, y \).
	Hence, \( A^2 + (b-a)A + (b-k)I - bJ = 0 \).
	We know that \( k \) is an eigenvalue of \( A \), and the corresponding eigenvector is \( \symbb 1 \).
	Since \( G \) is connected, \( k \) has multiplicity 1.

	Let \( \lambda \) be an eigenvalue of \( A \) such that \( \lambda \neq k \).
	Let \( x \) be the corresponding eigenvector.
	Applying the matrix equation to \( x \), we obtain \( \lambda^2 x + (b-a)\lambda x + (b-k)x = 0 \) as \( Jx = 0 \), as \( x \) is orthogonal to \( \symbb 1 \).
	Then \( \lambda^2 + (b-a)\lambda + (b-k) \) as \( x \neq 0 \).
	Hence,
	\[ \lambda = \frac{(a-b) \pm \sqrt{(a-b)^2 + 4(k-b)}}{2} \]
	In particular, there are only three possible eigenvalues for \( A \), which are \( k \) and the two possible solutions to the quadratic equation for \( \lambda \).
	Let \( \lambda, \mu \) be the solutions to the above equation.
	Let \( \lambda \) have multiplicity \( s \) and \( \mu \) have multiplicity \( t \).
	Then,
	\[ 0 = \tr A = \sum_{i=1}^n \lambda_i = s\lambda + t\mu + k \]
	We also have \( s + t + 1 = n \), since there are \( n \) eigenvalues.
	Solving both equations simultaneously, we obtain the result as desired.
\end{proof}
\begin{corollary}
	Let \( G \) be a Moore graph with \( \Delta(G) = k \).
	Then \( k \in \qty{2, 3, 7, 57} \).
\end{corollary}
\begin{proof}
	If \( G \) is a Moore graph, it is \( (k, 0, 1) \)-strongly regular on \( k^2 + 1 \) vertices.
	Then, one can check the condition in the previous theorem.
	\[ \frac{1}{2}\qty(k^2 \pm \frac{k^2 - 2k}{\sqrt{4k - 3}}) \in \mathbb Z \]
\end{proof}
\begin{remark}
	It is not known if such a graph \( G \) with \( k = 57 \) exists.
\end{remark}
